package org.example.myleet.p458;

/**
 * 官方解释：https://leetcode-cn.com/problems/poor-pigs/submissions/
 */
public class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int iteration = minutesToTest / minutesToDie;
        //代表i只小猪在j轮测试中最多可以判断多少个桶存在毒药
        int[][] dp = new int[buckets][iteration + 1];
        //初始化
        for (int i = 0; i < buckets; ++i) {
            //没有测试轮数的情况，只能判断1桶
            dp[i][0] = 1;
        }
        for (int j = 0; j <= iteration; ++j) {
            //没有小猪，只能判断1桶
            dp[0][j] = 1;
        }
        //组合数计算
        int[][] combination = new int[buckets + 1][buckets + 1];
        //动态规划
        for (int i = 1; i < buckets; ++i) {
            combination[i][0] = 1;
            combination[i][i] = 1;
            for (int deadPig = 1; deadPig < i; ++deadPig) {
                combination[i][deadPig] = combination[i - 1][deadPig] + combination[i - 1][deadPig - 1];
            }
            for (int j = 1; j <= iteration; j++) {
                for (int deadPig = 0; deadPig <= i; deadPig++) {
                    dp[i][j] += dp[i - deadPig][j - 1] * combination[i][deadPig];
                }
            }
            if (dp[i][iteration] >= buckets) {
                return i;
            }
        }
        return buckets - 1;
    }
}
